<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <title>蓝桥杯 | Hexo</title>
  <meta name="keywords" content="">
  <meta name="description" content="蓝桥杯 | Hexo">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="description" content="第二章 线性表线性表：表内数据类型相同，有限序列 本章将以总结的形式展现： 2.1 顺序表与链式表的区别     顺序表 链式表     存取 随机存取 顺序存取   结构 顺序存储（连续） 随机存储（不连续）   空间分配 静态存储（可以动态分配） 动态存储   操作 查找 O(1) ,插入和删除O（n） 查找 O(n) ,插入和删除O（1）   缺点 插入删除不便，长度不可以改变 查找速度慢，">
<meta property="og:type" content="article">
<meta property="og:title" content="数据结构">
<meta property="og:url" content="http://yoursite.com/2021/03/12/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/index.html">
<meta property="og:site_name" content="Hexo">
<meta property="og:description" content="第二章 线性表线性表：表内数据类型相同，有限序列 本章将以总结的形式展现： 2.1 顺序表与链式表的区别     顺序表 链式表     存取 随机存取 顺序存取   结构 顺序存储（连续） 随机存储（不连续）   空间分配 静态存储（可以动态分配） 动态存储   操作 查找 O(1) ,插入和删除O（n） 查找 O(n) ,插入和删除O（1）   缺点 插入删除不便，长度不可以改变 查找速度慢，">
<meta property="og:locale" content="en_US">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/23/171951-630686.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/23/171844-136893.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/19/203103-111988.jpeg">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/23/171839-101678.jpeg">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/23/200119-510473.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202103/05/113954-515448.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/23/203146-263519.jpeg">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/19/153239-688589.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/19/153248-836462.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/19/153259-101399.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202103/11/113055-306258.jpeg">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/19/151817-474283.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/02/103950-168345.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/02/105245-140913.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/19/153313-134836.png">
<meta property="article:published_time" content="2021-03-11T16:00:00.000Z">
<meta property="article:modified_time" content="2021-03-11T07:19:09.038Z">
<meta property="article:author" content="MOLU">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/23/171951-630686.png">


<link rel="icon" href="/img/avatar.jpg">

<link href="/css/style.css?v=1.1.0" rel="stylesheet">

<link href="/css/hl_theme/github.css?v=1.1.0" rel="stylesheet">

<link href="//cdn.jsdelivr.net/npm/animate.css@4.1.0/animate.min.css" rel="stylesheet">

<script src="//cdn.jsdelivr.net/npm/jquery@3.5.1/dist/jquery.min.js"></script>
<script src="/js/titleTip.js?v=1.1.0" ></script>

<script src="//cdn.jsdelivr.net/npm/highlightjs@9.16.2/highlight.pack.min.js"></script>
<script>
    hljs.initHighlightingOnLoad();
</script>

<script src="//cdn.jsdelivr.net/npm/nprogress@0.2.0/nprogress.min.js"></script>



<script src="//cdn.jsdelivr.net/npm/jquery.cookie@1.4.1/jquery.cookie.min.js" ></script>

<script src="/js/iconfont.js?v=1.1.0" ></script>

<meta name="generator" content="Hexo 5.0.0"></head>
<div style="display: none">
  <input class="theme_disqus_on" value="false">
  <input class="theme_preload_comment" value="">
  <input class="theme_blog_path" value="">
  <input id="theme_shortcut" value="true" />
</div>


<body>
<aside class="nav">
    <div class="nav-left">
        <a href="/" class="avatar_target">
    <img class="avatar" src="/img/avatar.jpg" />
</a>
<div class="author">
    <span>MOLU</span>
</div>

<div class="icon">
    
        
        <a title="rss" href="/atom.xml" target="_blank">
            
                <i class="iconfont icon-rss"></i>
            
        </a>
        
    
        
        <a title="github" href="https://github.com/molu-ggg" target="_blank">
            
                <i class="iconfont icon-github"></i>
            
        </a>
        
    
        
    
        
    
        
        <a title="email" href="mailto:2572876783@qq.com" target="_blank">
            
                <i class="iconfont icon-email"></i>
            
        </a>
        
    
</div>




<ul>
    <li><div class="all active" data-rel="All">All<small>(35)</small></div></li>
    
        
            
            <li><div data-rel="AI论文">AI论文<small>(5)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="专业知识">专业知识<small>(2)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="数学">数学<small>(2)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="机器学习">机器学习<small>(12)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="经典算法">经典算法<small>(10)</small></div>
                
            </li>
            
        
    
</ul>
<div class="left-bottom">
    <div class="menus">
    
    
    
    
    </div>
    <div><a class="about  hasFriend  site_url"  href="/about">About</a><a style="width: 50%"  class="friends">Friends</a></div>
</div>
<input type="hidden" id="yelog_site_posts_number" value="35">

<div style="display: none">
    <span id="busuanzi_value_site_uv"></span>
    <span id="busuanzi_value_site_pv"></span>
</div>

    </div>
    <div class="nav-right">
        <div class="friends-area">
    <div class="friends-title">
        Links
        <i class="iconfont icon-left"></i>
    </div>
    <div class="friends-content">
        <ul>
            
            <li><a target="_blank" href="http://yelog.org/">叶落阁</a></li>
            
        </ul>
    </div>
</div>
        <div class="title-list">
    <div class="right-top">
        <div id="default-panel">
            <i class="iconfont icon-search" data-title="搜索 快捷键 i"></i>
            <div class="right-title">All</div>
            <i class="iconfont icon-file-tree" data-title="切换到大纲视图 快捷键 w"></i>
        </div>
        <div id="search-panel">
            <i class="iconfont icon-left" data-title="返回"></i>
            <input id="local-search-input" />
            <label class="border-line" for="input"></label>
            <i class="iconfont icon-case-sensitive" data-title="大小写敏感"></i>
            <i class="iconfont icon-tag" data-title="标签"></i>
        </div>
        <div id="outline-panel" style="display: none">
            <div class="right-title">大纲</div>
            <i class="iconfont icon-list" data-title="切换到文章列表"></i>
        </div>
    </div>

    <div class="tags-list">
    <input id="tag-search" />
    <div class="tag-wrapper">
        
            <li class="article-tag-list-item">
                <i class="iconfont icon-tag"></i><a>50</a>
            </li>
        
            <li class="article-tag-list-item">
                <i class="iconfont icon-tag"></i><a>AI</a>
            </li>
        
            <li class="article-tag-list-item">
                <i class="iconfont icon-tag"></i><a>数据结构，最短路径，图</a>
            </li>
        
            <li class="article-tag-list-item">
                <i class="iconfont icon-tag"></i><a>机器学习</a>
            </li>
        
            <li class="article-tag-list-item">
                <i class="iconfont icon-tag"></i><a>相似度计算</a>
            </li>
        
    </div>

</div>

    
    <div id="local-search-result">

    </div>
    
    <nav id="title-list-nav">
        
        <a id="top" class="All 经典算法 "
           href="/2020/07/20/b_leetcode/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="leetcode &amp; 蓝桥">leetcode &amp; 蓝桥</span>
            <span class="post-date" title="2020-07-20 00:00:00">2020/07/20</span>
        </a>
        
        <a id="top" class="All AI论文 "
           href="/2020/07/10/d_GAT/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="GAT">GAT</span>
            <span class="post-date" title="2020-07-10 08:50:20">2020/07/10</span>
        </a>
        
        <a  class="All 专业知识 "
           href="/2021/03/12/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="计算机组成原理">计算机组成原理</span>
            <span class="post-date" title="2021-03-12 00:00:00">2021/03/12</span>
        </a>
        
        <a  class="All 专业知识 "
           href="/2021/03/12/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="数据结构">数据结构</span>
            <span class="post-date" title="2021-03-12 00:00:00">2021/03/12</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2020/12/05/b_%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E4%B8%8E%E8%AE%B0%E5%BF%86%E5%8C%96%E6%90%9C%E7%B4%A2/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="动态规划记忆化">动态规划记忆化</span>
            <span class="post-date" title="2020-12-05 00:00:00">2020/12/05</span>
        </a>
        
        <a  class="All AI论文 "
           href="/2020/07/25/d_300-paperDAT/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="DAT for recommender">DAT for recommender</span>
            <span class="post-date" title="2020-07-25 08:50:20">2020/07/25</span>
        </a>
        
        <a  class="All 数学 "
           href="/2020/07/20/a_%E7%AE%97%E6%B3%95/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="算法总结">算法总结</span>
            <span class="post-date" title="2020-07-20 00:00:00">2020/07/20</span>
        </a>
        
        <a  class="All 数学 "
           href="/2020/07/20/a_%E6%95%B0%E5%AD%A6/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="数学">数学</span>
            <span class="post-date" title="2020-07-20 00:00:00">2020/07/20</span>
        </a>
        
        <a  class="All "
           href="/2020/07/05/%E5%AF%B9%E9%9A%90%E7%A7%98%E7%9A%84%E8%A7%92%E8%90%BD%E7%94%B5%E8%A7%86%E5%89%A7%E7%9A%84%E6%84%9F%E6%82%9F%E4%BB%A5%E5%8F%8A%E8%AE%A4%E8%AF%86/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="对隐秘的角落电视剧的感悟以及认识">对隐秘的角落电视剧的感悟以及认识</span>
            <span class="post-date" title="2020-07-05 00:00:00">2020/07/05</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2020/07/04/a_%E6%A8%A1%E6%9D%BF%E5%BA%93/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="模板库">模板库</span>
            <span class="post-date" title="2020-07-04 08:50:20">2020/07/04</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2020/07/04/a_%E7%99%BE%E5%BA%A6%E6%8A%80%E6%9C%AF%E8%AE%A4%E8%AF%81/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="百度技术认证">百度技术认证</span>
            <span class="post-date" title="2020-07-04 08:50:20">2020/07/04</span>
        </a>
        
        <a  class="All AI论文 "
           href="/2020/07/01/d_GCN%E8%AE%BA%E6%96%87%E8%A7%A3%E8%AF%BB/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="GCN">GCN</span>
            <span class="post-date" title="2020-07-01 08:50:20">2020/07/01</span>
        </a>
        
        <a  class="All AI论文 "
           href="/2020/06/04/d_word2vec_node2vec/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="Word2vec &amp; Node2vec">Word2vec &amp; Node2vec</span>
            <span class="post-date" title="2020-06-04 08:50:20">2020/06/04</span>
        </a>
        
        <a  class="All AI论文 "
           href="/2020/05/05/d_GAN/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="GAN">GAN</span>
            <span class="post-date" title="2020-05-05 08:50:20">2020/05/05</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2020/05/04/d_Deepwalk/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="DEEPWALK">DEEPWALK</span>
            <span class="post-date" title="2020-05-04 08:50:20">2020/05/04</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2020/02/15/b_%E8%B4%AA%E5%BF%83/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="贪心与动态规划">贪心与动态规划</span>
            <span class="post-date" title="2020-02-15 00:00:00">2020/02/15</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2020/02/12/a_2020/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="机器学习零散知识记录">机器学习零散知识记录</span>
            <span class="post-date" title="2020-02-12 00:00:00">2020/02/12</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2020/02/12/b_%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="动态规划——背包问题">动态规划——背包问题</span>
            <span class="post-date" title="2020-02-12 00:00:00">2020/02/12</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2020/02/03/b_%E8%93%9D%E6%A1%A5%E6%9D%AF%E7%BB%83%E4%B9%A0%E9%A2%98/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="蓝桥杯">蓝桥杯</span>
            <span class="post-date" title="2020-02-03 00:00:00">2020/02/03</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2020/01/20/c_%E5%86%B3%E7%AD%96%E6%A0%91/"
           data-tag="50"
           data-author="" >
            <span class="post-title" title="决策树总结">决策树总结</span>
            <span class="post-date" title="2020-01-20 00:00:00">2020/01/20</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2020/01/12/b_%E5%85%A8%E6%8E%92%E5%88%97/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="全排列">全排列</span>
            <span class="post-date" title="2020-01-12 00:00:00">2020/01/12</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2019/12/02/b_%E6%9C%89%E7%A9%B7%E8%87%AA%E5%8A%A8%E6%9C%BA/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="有穷自动机">有穷自动机</span>
            <span class="post-date" title="2019-12-02 00:00:00">2019/12/02</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2019/11/20/b_%E9%94%99%E6%8E%92%E5%85%AC%E5%BC%8F/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="错排公式">错排公式</span>
            <span class="post-date" title="2019-11-20 00:00:00">2019/11/20</span>
        </a>
        
        <a  class="All "
           href="/2019/10/29/a_%E5%BC%97%E6%B4%9B%E4%BC%8A%E5%BE%B7/"
           data-tag="数据结构，最短路径，图"
           data-author="" >
            <span class="post-title" title="最短路径之弗洛伊德算法">最短路径之弗洛伊德算法</span>
            <span class="post-date" title="2019-10-29 00:00:00">2019/10/29</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/08/04/c_BPR/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="贝叶斯">贝叶斯</span>
            <span class="post-date" title="2019-08-04 08:50:20">2019/08/04</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/08/02/c_matrix/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="矩阵分解与正则化">矩阵分解与正则化</span>
            <span class="post-date" title="2019-08-02 08:25:59">2019/08/02</span>
        </a>
        
        <a  class="All "
           href="/2019/07/28/c_coordination1/"
           data-tag="AI,机器学习,相似度计算"
           data-author="" >
            <span class="post-title" title="协同过滤-上">协同过滤-上</span>
            <span class="post-date" title="2019-07-28 08:25:59">2019/07/28</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/07/26/c_cnn/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="cnn">cnn</span>
            <span class="post-date" title="2019-07-26 18:54:51">2019/07/26</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/07/22/c_coordination2/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="协同过滤—下">协同过滤—下</span>
            <span class="post-date" title="2019-07-22 18:54:26">2019/07/22</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/07/22/c_kmeans/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="K-means算法">K-means算法</span>
            <span class="post-date" title="2019-07-22 18:53:07">2019/07/22</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/07/21/c_nerve2/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="神经网络-下">神经网络-下</span>
            <span class="post-date" title="2019-07-21 11:37:18">2019/07/21</span>
        </a>
        
        <a  class="All "
           href="/2019/07/20/c_nerve1/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="神经网络—上">神经网络—上</span>
            <span class="post-date" title="2019-07-20 17:29:10">2019/07/20</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/06/22/c_gradient/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="线性回归与梯度下降算法">线性回归与梯度下降算法</span>
            <span class="post-date" title="2019-06-22 08:26:36">2019/06/22</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/06/19/c_flyback/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="线性回归">线性回归</span>
            <span class="post-date" title="2019-06-19 00:00:00">2019/06/19</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2019/05/20/b_%E8%A7%86%E9%A2%91%E7%BB%8F%E5%85%B8%E7%AE%97%E6%B3%95/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="简单入门算法">简单入门算法</span>
            <span class="post-date" title="2019-05-20 00:00:00">2019/05/20</span>
        </a>
        
        <div id="no-item-tips">

        </div>
    </nav>
    <div id="outline-list">
    </div>
</div>
    </div>
    <div class="hide-list">
        <div class="semicircle" data-title="切换全屏 快捷键 s">
            <div class="brackets first"><</div>
            <div class="brackets">&gt;</div>
        </div>
    </div>
</aside>
<div id="post">
    <div class="pjax">
        <article id="post-b_蓝桥杯练习题" class="article article-type-post" itemscope itemprop="blogPost">
    
        <h1 class="article-title">蓝桥杯</h1>
    
    <div class="article-meta">
        
        
        
        <span class="book">
            <i class="iconfont icon-category"></i>
            
            
            <a  data-rel="经典算法">经典算法</a>
            
        </span>
        
        
    </div>
    <div class="article-meta">
        
            Created At : <time class="date" title='Updated At: 2020-08-09 15:17:46'>2020-02-03 00:00</time>
        
    </div>
    <div class="article-meta">
        
        
        <span id="busuanzi_container_page_pv">
            Views 👀 :<span id="busuanzi_value_page_pv">
                <span class="count-comment">
                    <span class="spinner">
                      <div class="cube1"></div>
                      <div class="cube2"></div>
                    </span>
                </span>
            </span>
        </span>
        
        
    </div>
    
    <div class="toc-ref">
    
        <ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#Anagrams%E9%97%AE%E9%A2%98"><span class="toc-text">Anagrams问题</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E6%95%B0%E5%AD%97%E6%B8%B8%E6%88%8F"><span class="toc-text">数字游戏</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%95%B0%E7%BB%84%E6%B1%82%E5%92%8C"><span class="toc-text">数组求和</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%AD%97%E7%AC%A6%E4%B8%B2%E5%8E%8B%E7%BC%A9"><span class="toc-text">字符串压缩</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%92%8C%E8%B0%90%E5%AE%BF%E8%88%8D2"><span class="toc-text">和谐宿舍2</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%9C%A8%E6%A3%8D%EF%BC%9A%E4%B8%80%E9%81%93%E5%A5%BD%E9%A2%98"><span class="toc-text">木棍：一道好题</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E8%AF%95%E9%A2%98-%E7%AE%97%E6%B3%95%E6%8F%90%E9%AB%98-%E6%89%BE%E7%B4%A0%E6%95%B0"><span class="toc-text">试题 算法提高 找素数</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%AE%97%E6%B3%95%E8%AE%AD%E7%BB%83-%E4%B9%98%E6%B3%95%E6%AC%A1%E6%95%B0"><span class="toc-text">算法训练 乘法次数</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E7%BA%BF%E6%AE%B5%E6%A0%91"><span class="toc-text">线段树</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%93%8D%E4%BD%9C%E6%A0%BC%E5%AD%90%E2%80%94%E2%80%94%E7%BA%BF%E6%AE%B5%E6%A0%91"><span class="toc-text">操作格子——线段树</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%80%9D%E6%83%B3%EF%BC%9A"><span class="toc-text">思想：</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E9%80%92%E5%BD%92%E5%87%BA%E5%8F%A3%EF%BC%9A"><span class="toc-text">递归出口：</span></a></li></ol></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E8%83%BD%E9%87%8F%E9%A1%B9%E9%93%BE%EF%BC%9A"><span class="toc-text">能量项链：</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%9F%B3%E5%AD%90%E5%90%88%E5%B9%B6%EF%BC%9A"><span class="toc-text">石子合并：</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B9%9D%E5%AE%AB%E9%87%8D%E6%8E%92%EF%BC%9A"><span class="toc-text">九宫重排：</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%9C%80%E5%A4%A7%E5%80%BC%E8%B7%AF%E5%BE%84"><span class="toc-text">最大值路径</span></a></li><li class="toc-item toc-level-2"><a class="toc-link"><span class="toc-text"> </span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%9F%A9%E9%98%B5%E7%BF%BB%E8%BD%AC%EF%BC%88%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%EF%BC%89"><span class="toc-text">矩阵翻转（动态规划）</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%EF%BC%88%E6%9C%AA%E8%A7%A3%E5%86%B3%EF%BC%89"><span class="toc-text">（未解决）</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%96%91%E9%97%AE%EF%BC%9F%EF%BC%9F%EF%BC%9F"><span class="toc-text">疑问？？？</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%AD%A6%E4%B9%A0string%E5%87%A0%E4%B8%AA%E5%87%BD%E6%95%B0%EF%BC%9A"><span class="toc-text">学习string几个函数：</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91%EF%BC%9A"><span class="toc-text">最小生成树：</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%B9%B6%E6%9F%A5%E9%9B%86%EF%BC%9A-%E4%B8%89%E5%87%BD%E6%95%B0%E8%A1%A8%E7%A4%BA"><span class="toc-text">并查集：(三函数表示)</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%85%8B%E9%B2%81%E6%96%AF%E5%8D%A1%E5%B0%94%EF%BC%9A"><span class="toc-text">克鲁斯卡尔：</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E7%94%B1%E7%82%B9%E9%81%8D%E5%8E%86%E8%BE%B9%E7%9A%84%E4%B8%89%E6%95%B0%E7%BB%84%EF%BC%9A"><span class="toc-text">由点遍历边的三数组：</span></a></li></ol></li></ol></li></ol>
    
<style>
    .left-col .switch-btn,
    .left-col .switch-area {
        display: none;
    }
    .toc-level-4 i,
    .toc-level-4 ol {
        display: none !important;
    }
</style>
</div>
    
    <div class="article-entry" itemprop="articleBody">
      
        <p>前缀表达式：</p>
<p>吸取经验，一定要认真审题，提取关键词！</p>
<h1 id="Anagrams问题"><a href="#Anagrams问题" class="headerlink" title="Anagrams问题"></a>Anagrams问题</h1><p>以后要带上初始化工作</p>
<h1 id="数字游戏"><a href="#数字游戏" class="headerlink" title="数字游戏"></a>数字游戏</h1><blockquote>
<p>问题描述</p>
<p>　　给定一个1～N的排列a[i]，每次将相邻两个数相加，得到新序列，再对新序列重复这样的操作，显然每次得到的序列都比上一次的序列长度少1，最终只剩一个数字。<br>　　例如:<br>　　3 1 2 4<br>　　4 3 6<br>　　7 9<br>　　16<br>　　现在如果知道N和最后得到的数字sum，请求出最初序列a[i]，为1～N的一个排列。若有多种答案，则输出字典序最小的那一个。数据保证有解。</p>
</blockquote>
<p>这是一个杨辉三角</p>
<pre><code class="lang-c++">#include&lt;bits\stdc++.h&gt;
using namespace std;


long long int a[100][100],b[100];

int main()&amp;#123;


    a[1][1]=1;
    for(int i=1;i&lt;=10;i++) b[i]=i;
    for(int i=2;i&lt;=10;i++)&amp;#123;

       for(int j=1;j&lt;=i;j++)&amp;#123;
            a[i][j]=a[i-1][j-1]+a[i-1][j];
       &amp;#125;
    &amp;#125;
    long long int n,m;
    cin&gt;&gt;n&gt;&gt;m;
    do&amp;#123;
        int sum=0;
        for(int i=1;i&lt;=n;i++)&amp;#123;
            sum+=a[n][i]*b[i];
        &amp;#125;
        if(sum==m) &amp;#123;
            for(int i=1;i&lt;=n;i++)&amp;#123;
                cout&lt;&lt;b[i]&lt;&lt;&quot; &quot;;

            &amp;#125;
            break;
        &amp;#125;

    &amp;#125;while(next_permutation(b+1,b+1+n));


&amp;#125;
</code></pre>
<p>试题 算法提高 宰羊</p>
<p>这道题是区间DP，到底是什么意思那？</p>
<h2 id="数组求和"><a href="#数组求和" class="headerlink" title="数组求和"></a>数组求和</h2><p><a target="_blank" rel="noopener" href="http://lx.lanqiao.cn/problem.page?gpid=T582#submitpanel">提交此题</a>  </p>
<pre><code class="lang-c++">#include&lt;bits\stdc++.h&gt;
using namespace std;

int main()&amp;#123;
    int m,n;
    int a[100010];
    int i,j;
    cin&gt;&gt;n;
    cin&gt;&gt;m;
    for(i=1;i&lt;=n;i++)&amp;#123;
        cin&gt;&gt;a[i];
        a[i+n]=a[i];
    &amp;#125;

    long long int  max1=-999999;//这个必须的！！！ 
    for(i=1;i&lt;=n;i++)&amp;#123;
        int sum=0;
        for(j=0;j&lt;m;j++)&amp;#123;
            sum+=a[i+j];

        &amp;#125;
            if(sum&gt;max1) &amp;#123;//亏死了，你居然把它放在里面！ 
                max1=sum;

            &amp;#125;
    &amp;#125;
    cout&lt;&lt;max1;
&amp;#125;
</code></pre>
<h2 id="字符串压缩"><a href="#字符串压缩" class="headerlink" title="字符串压缩"></a>字符串压缩</h2><p> 主要：带有空格的字符串应该如何处理：</p>
<p><strong>是不是</strong></p>
<pre><code class="lang-c++">       char c[100010];
       cin.get(c,100010);
       for(int i=0;c[i]!=&#39;\0&#39;;i++)&amp;#123;
</code></pre>
<pre><code class="lang-c++">#include&lt;bits\stdc++.h&gt;
using namespace std;

vector &lt;char&gt; s;
int  a[100010];
int main()&amp;#123;

   memset(a,0,sizeof(a));
   char c[100010];


       cin.get(c,100010);
       for(int i=0;c[i]!=&#39;\0&#39;;i++)&amp;#123;
    char ch=c[i];
        a[ch]++;
        if(ch==&#39; &#39;) s.push_back(ch);
        else if(a[ch]==1||a[ch]==3||a[ch]==6) s.push_back(ch);
   &amp;#125;

    for(int i=0;i&lt;s.size();i++)&amp;#123;
        cout&lt;&lt;s[i];
    &amp;#125;
    cout&lt;&lt;endl;

&amp;#125;
</code></pre>
<h2 id="和谐宿舍2"><a href="#和谐宿舍2" class="headerlink" title="和谐宿舍2"></a>和谐宿舍2</h2><p>10分钟写一个程序，一个半小时调试</p>
<p>问题描述</p>
<p>　　我的某室友学过素描，墙上有n张他的作品。这些作品都是宽度为1，高度不定的矩形，从左到右排成一排，且底边在同一水平线上。<br>　　宿舍评比就要来了，为了及格，我们决定买不多于m块的矩形木板，把这些作品和谐掉。要求木板也从左到右排成一排，且底边与作品的底边在同一水平线上。<br>　　在能够把所有作品和谐掉的前提下，我们希望这些木板的面积和最小，问最小面积和。</p>
<pre><code class="lang-c++">#include&lt;bits\stdc++.h&gt;
using namespace std;


int a[1000];
int maxz[1000];
int F[1000][1000];

int mini(int y,int x)&amp;#123;

    if(x==0) return y;
    else return min(y,x);
&amp;#125;
int main()&amp;#123;

  int i,j;
  int n,m,k;
  int max1=0;
  cin&gt;&gt;n&gt;&gt;m;

  //化时间为空间 
  for(i=1;i&lt;=n;i++)&amp;#123;
      cin&gt;&gt;a[i];
      if(max1&lt;a[i]) max1=a[i];
      maxz[i]=max1;//前i的最大值 

  &amp;#125;
  int qumax[105][105];
  for(i=0;i&lt;=n;i++)&amp;#123;
      int m=0;
      for(j=i;j&lt;=n;j++)&amp;#123;
          if(m&lt;a[j]) m=a[j];
          qumax[i][j]=m;//某区间的最大值 
          //cout&lt;&lt;qumax[i][j]&lt;&lt;&quot; &quot;;
      &amp;#125;
      //cout&lt;&lt;endl;

  &amp;#125; 
  //开始DP 
memset(F,0,sizeof(F)); 
  for(i=1;i&lt;=n;i++)&amp;#123;//到了第几块 
      for(j=1;j&lt;=m;j++)&amp;#123;//用几块木板 
          if(j&gt;i) F[i][j]=-1;
          if(j==1)&amp;#123;
              F[i][j]=qumax[1][i]*(i);//i,j,k混乱
          //    cout&lt;&lt;i&lt;&lt;&quot; &quot;&lt;&lt;j&lt;&lt;&quot; &quot;&lt;&lt;k&lt;&lt;&quot; &quot;&lt;&lt;F[i][j]&lt;&lt;endl;
          &amp;#125;
        else &amp;#123;
            for(k=i-1;k&gt;=1;k--)&amp;#123;//
               if (F[k][j-1]==-1) break;
               if(F[i][j]==0) F[i][j]=F[k][j-1]+qumax[k+1][i]*(i-k);
            else F[i][j]=min(F[k][j-1]+qumax[k+1][i]*(i-k),F[i][j]);
            //失败之处：    i,j,k混乱！！！！！
            &amp;#125;
        &amp;#125;
        //cout&lt;&lt;F[i][j]&lt;&lt;&quot; &quot;;
    &amp;#125;
//    cout&lt;&lt;endl;
&amp;#125;
      cout&lt;&lt;F[n][m];
</code></pre>
<h2 id="木棍：一道好题"><a href="#木棍：一道好题" class="headerlink" title="木棍：一道好题"></a>木棍：一道好题</h2><h2 id="试题-算法提高-找素数"><a href="#试题-算法提高-找素数" class="headerlink" title="试题 算法提高 找素数"></a>试题 算法提高 找素数</h2><p><a target="_blank" rel="noopener" href="http://lx.lanqiao.cn/problem.page?gpid=T267#submitpanel">提交此题</a>  </p>
<p>资源限制</p>
<p>时间限制：1.0s   内存限制：256.0MB</p>
<p>问题描述</p>
<p>　　给定区间[L, R] ， 请计算区间中素数的个数。</p>
<p>输入格式</p>
<p>　　两个数L和R。</p>
<p>输出格式</p>
<p>　　一行，区间中素数的个数。</p>
<p>样例输入</p>
<p>2 11</p>
<p>样例输出</p>
<p>5</p>
<p>数据规模和约定</p>
<p>　　2 &lt;= L &lt;= R &lt;= 2147483647 R-L &lt;= 1000000</p>
<p>素数晒的升级版：</p>
<p><strong>R-L &lt;= 1000000</strong>关键条件：</p>
<p><strong>素数，合数的本质因素：前sqrt（n)中是否有因子！</strong></p>
<p>用sqrt(N)之前的素数去找 [r,l] 映射的区间 [0,l-r] 的数</p>
<pre><code class="lang-c++">#include&lt;bits\stdc++.h&gt;
using namespace std;

bool a[91499748];//1是合数 
bool c[1001000];
int su[1000000];
int main()&amp;#123;

    int m,n,sum=0;
    cin&gt;&gt;m&gt;&gt;n;
    int cnt=0;
    //合数被小于等于是sqrt(q)的数筛选掉！
    //先找到他之前的质数，然后映射[l,r]到【0，r-l】区间里即可 
    memset(a,0,sizeof(a)); 
     //前sqrt(n)质数已经找到 

    for(int i=2;i&lt;=sqrt(n);i++)&amp;#123;

        if(i&lt;=m)&amp;#123;
                if(a[i]==0)//是素数
           su[++cnt]=i;
         for(int j=1;j&lt;=cnt&amp;&amp;su[j]*i&lt;=sqrt(n);j++)&amp;#123;
             long long int k=su[j];
             a[k*i]=1;
             if(i%su[j]==0) break;
         &amp;#125;
        &amp;#125;    
        &amp;#125;
    //只专注于后面的sqrt(n)

    for(int i=m;i&lt;=n;i++)&amp;#123;
        for(int j=1;j&lt;=cnt;j++) &amp;#123;
             if(i%su[j]==0) &amp;#123;
             c[i-m]=1;//是合数    
             break;
        &amp;#125;
        &amp;#125;
    &amp;#125;


    for(int i=m;i&lt;=n;i++)&amp;#123;
    if(c[i-m]==0)  sum++;    
    &amp;#125; 
    cout&lt;&lt;sum;
    return 0;
&amp;#125;
</code></pre>
<h2 id="算法训练-乘法次数"><a href="#算法训练-乘法次数" class="headerlink" title="算法训练 乘法次数"></a>算法训练 乘法次数</h2><p>问题描述</p>
<p>　　给你一个非零整数，让你求这个数的n次方，每次相乘的结果可以在后面使用，求至少需要多少次乘。如24：2<em>2=22（第一次乘），22</em>22=24（第二次乘），所以最少共2次；</p>
<p>输入格式</p>
<p>　　第一行m表示有m(1&lt;=m&lt;=100)组测试数据；<br>　　每一组测试数据有一整数n（0&lt;n&lt;=100000000）;</p>
<p>试用乘法幂解决</p>
<h1 id="线段树"><a href="#线段树" class="headerlink" title="线段树"></a>线段树</h1><h2 id="操作格子——线段树"><a href="#操作格子——线段树" class="headerlink" title="操作格子——线段树"></a>操作格子——线段树</h2><p>此题为：</p>
<p><a target="_blank" rel="noopener" href="http://lx.lanqiao.cn/problem.page?gpid=T18#submitpanel">提交此题</a>  </p>
<p>资源限制</p>
<p>时间限制：1.0s   内存限制：256.0MB</p>
<p>问题描述</p>
<p>有n个格子，从左到右放成一排，编号为1-n。</p>
<p>共有m次操作，有3种操作类型：</p>
<p>1.修改一个格子的权值，</p>
<p>2.求连续一段格子权值和，</p>
<p>3.求连续一段格子的最大值。</p>
<p>对于每个2、3操作输出你所求出的结果。</p>
<p>输入格式</p>
<p>第一行2个整数n，m。</p>
<p>接下来一行n个整数表示n个格子的初始权值。</p>
<p>接下来m行，每行3个整数p,x,y，p表示操作类型，p=1时表示修改格子x的权值为y，p=2时表示求区间[x,y]内格子权值和，p=3时表示求区间[x,y]内格子最大的权值。</p>
<p>输出格式</p>
<p>有若干行，行数等于p=2或3的操作总数。</p>
<p>每行1个整数，对应了每个p=2或3操作的结果。</p>
<p>样例输入</p>
<blockquote>
<p>4 3</p>
<p>1 2 3 4</p>
<p>2 1 3</p>
<p>1 4 3</p>
<p>3 1 4</p>
<p>样例输出</p>
<p>6</p>
<p>3</p>
<p>数据规模与约定</p>
<p>对于20%的数据n &lt;= 100，m &lt;= 200。</p>
<p>对于50%的数据n &lt;= 5000，m &lt;= 5000。</p>
<p>对于100%的数据1 &lt;= n &lt;= 100000，m &lt;= 100000，0 &lt;= 格子权值 &lt;= 10000。</p>
<p>这是线段树的模板题，</p>
<p>我们要学会：思想，函数操作，应用</p>
</blockquote>
<h3 id="思想："><a href="#思想：" class="headerlink" title="思想："></a>思想：</h3><p>他是一棵二叉搜索树，是平衡二叉树，明显的二分递归区间，直到每个区间只有一个叶节点</p>
<p>特征：区间树类似，是完全二叉树！（不是满二叉树）</p>
<p><img src="https://moluggg.oss-cn-qingdao.aliyuncs.com/img/20200313181358.png"/></p>
<p>如图，就是将区间分呀分，每一个区间含有一个值，一般而言，应该是有序的值。</p>
<p>当然也可以无序，无序的话，只能通过结点来表示与操作。</p>
<p>这道题，起先是有序的初始化，无序的数插入的操作。</p>
<p>首先，要学会他的初始化：</p>
<p>先定义一个结构体，存储tree的每一个结点的内容</p>
<pre><code class="lang-c++">struct node &amp;#123;
    long long int  max1,sum1;
    long long int left,right;
&amp;#125;a[400010];
</code></pre>
<p>初始化 ：</p>
<pre><code class="lang-c++">void xds(ll i,ll start,ll end)&amp;#123;//建树并初始化 
    a[i].left=start,a[i].right=end;
    if(start==end)&amp;#123;
        a[i].sum1=input[++cnt];
        a[i].max1=input[cnt];//一定要看数据范围 ,input是输入值，是有序的输入，有序的放置
        return ;//递归操作少不了return
    &amp;#125;
    int mid=(start+end)&gt;&gt;1;//二分思想关键
    xds(2*i,start,mid);
    xds(2*i+1,mid+1,end);
    a[i].sum1=a[i*2].sum1+a[i*2+1].sum1;//回溯求和以及最大值
    a[i].max1=max(a[i*2].max1,a[i*2+1].max1);
&amp;#125;
</code></pre>
<p>修改某一位置的值:</p>
<p>与建树基本一样，建树是区间范围</p>
<p>而修改值是找特定的位置x，从i开始遍历，并改成value</p>
<pre><code class="lang-c++">void change(ll i,ll x,ll value)&amp;#123;//第i个值修改成k ,

    if(x==a[i].left&amp;&amp;x==a[i].right)&amp;#123;
        a[i].sum1=value;
        a[i].max1=value;
        return;
    &amp;#125;

    ll mid=(a[i].left+a[i].right)&gt;&gt;1;
    if(x&lt;=mid) change(2*i,x,value);
    else change(2*i+1,x,value);

    a[i].sum1=a[i*2].sum1+a[i*2+1].sum1;
    a[i].max1=max(a[i*2].max1,a[i*2+1].max1);
&amp;#125;
</code></pre>
<p>查找区间的最大值和求和</p>
<p>思路：（以求和为例）</p>
<h4 id="递归出口："><a href="#递归出口：" class="headerlink" title="递归出口："></a>递归出口：</h4><p>当tree（也就是a）的左右儿子完全被要查询的区间<strong>完全包含</strong>，则返回该区间的和。</p>
<p>如果不是：</p>
<p>if  要查询的区间的左极端比tree右端点还小，则无解，要查询的区间的右极端比tree左端点还小，<strong>完全不包含关系</strong>，无解</p>
<p>==else：<strong>不完全包含，重叠</strong>关系处理方法：（难点）==</p>
<p><img src="file:///D:\360MoveData\Users\陌路放歌\Documents\Tencent Files\2572876783\Image\C2C\Image1\{1CEF4B96-6AE3-5463-3C2B-EE94C5D2769E}.png" alt="img"></p>
<p>上面黑色部分是要查找的区间,如果数据合理的话,刚开始的区间比我们要查找的区间要大,满满的缩短区间大小,直到某一区间的子区间不能完全包含要查找的区间</p>
<p>这样,我们就要找出这种情况,并在分治:</p>
<p>如果s&lt;a[i*2].right 说明i的左子区间有数,需要再递归寻找</p>
<p>如果e&gt;a[i*2+1].left 说明i的右子区间有数,需要再递归划分,</p>
<p>这样递归划分的出口是:存在k=i,k区间完全被查找区间包含,返回他们区间的最大值</p>
<p><strong>当然，可存在要查询的区间同时满足上面两种情况</strong></p>
<pre><code class="lang-c++">ll find_sum(ll i,ll s,ll e)&amp;#123;//不太一样 
    //包含关系 :查找范围包含树 
    if(s&lt;=a[i].left&amp;&amp;e&gt;=a[i].right)&amp;#123;
        return a[i].sum1;//是的话已经结束，不是的话继续： 
    &amp;#125;
    if(a[i].right&lt;s||a[i].left&gt;e) return 0;//区间没有交集
    ll sum=0; 

    if(a[i*2].right&gt;=s) sum+=find_sum(i*2,s,e);

    if(a[i*2+1].left&lt;=e) sum+=find_sum(i*2+1,s,e);

    return sum;

&amp;#125;
ll find_max(ll i,ll s,ll e)&amp;#123;
    if(s&lt;=a[i].left&amp;&amp;e&gt;=a[i].right)&amp;#123;
        return a[i].max1;//是的话已经结束，不是的话继续： 
    &amp;#125;
    if(a[i].right&lt;s||a[i].left&gt;e) return 0;//区间没有交集
    ll maxn=0;//
    if(a[i*2].right&gt;=s) maxn=max(maxn,find_max(i*2,s,e));
    if(a[i*2+1].left&lt;=e) maxn=max(maxn,find_max(i*2+1,s,e));
    return maxn;
&amp;#125;
</code></pre>
<p>主函数：</p>
<pre><code class="lang-c++">int main()&amp;#123;
    ll n,k,m,value;
    ll i,j;

    cin&gt;&gt;n&gt;&gt;m；
    for(i=1;i&lt;=n;i++)&amp;#123;
        cin&gt;&gt;k;
        input[i]=k;
    //    insert(1,i,input[i]);//从1开始 
    &amp;#125;
    xds(1,1,n);//框架给弄好
    for (i=1;i&lt;=m;i++)&amp;#123;
        int x,y,p;
        cin&gt;&gt;p&gt;&gt;x&gt;&gt;value;
        if(p==1)&amp;#123;
            change(1,x,value);
        &amp;#125;
        if(p==2)&amp;#123;
            cout&lt;&lt;find_sum(1,x,value)&lt;&lt;endl;
        &amp;#125;
        if(p==3)&amp;#123;
            cout&lt;&lt;find_max(1,x,value)&lt;&lt;endl; 
        &amp;#125;
    &amp;#125;

&amp;#125;
</code></pre>
<pre><code class="lang-c++">//date 20140123
 2 #include &lt;cstdio&gt;
 3 #include &lt;cstring&gt;
 4 
 5 const int maxn = 505;
 6 const int INF = 9999999;
 7 
 8 inline int getint()
 9 &amp;#123;
10     int ans(0);  char w = getchar();
11     while(w &lt; &#39;0&#39; || w &gt; &#39;9&#39;)w = getchar();
12     while(&#39;0&#39; &lt;= w &amp;&amp; w &lt;= &#39;9&#39;)
13     &amp;#123;
14         ans = ans * 10 + w - &#39;0&#39;;
15         w = getchar();
16     &amp;#125;
17     return ans;
18 &amp;#125;
19 
20 inline int max(int a, int b)&amp;#123;return a &gt; b ? a : b;&amp;#125;
21 inline int min(int a, int b)&amp;#123;return a &lt; b ? a : b;&amp;#125;
22 
23 int n;
24 int a[maxn];
25 int count[maxn], count2[maxn];
26 int sum[maxn];
27 int exist[maxn];
28 int g[maxn][maxn];
29 int f[maxn];
30 
31 inline int check(int l, int r)
32 &amp;#123;
33     memset(exist, 0, sizeof exist);
34     for(int i = l; i &lt;= r; ++i)if(exist[a[i]])return false;
35     else ++exist[a[i]];
36     for(int i = 1; i &lt;= r - l + 1; ++i)if(!exist[i])return false;
37     return true;
38 &amp;#125;
39 
40 int main()
41 &amp;#123;
42     freopen(&quot;matryoshka.in&quot;, &quot;r&quot;, stdin);
43     freopen(&quot;matryoshka.out&quot;, &quot;w&quot;, stdout);
44 
45     n = getint();
46     for(int i = 1; i &lt;= n; ++i)    a[i] = getint();
47     memset(g, 0x7F, sizeof g);
48     for(int i = n; i; --i)
49     &amp;#123;
50         g[i][i] = 0;
51         for(int j = i + 1; j &lt;= n; ++j)
52         &amp;#123;
53             g[i][j] = INF;
54             int Max(0), flag(0), Min1(INF), Min2(INF), ans(INF), Min(INF);
55             memset(count2, 0, sizeof count2);
56             memset(count, 0, sizeof count);
57             
58             for(int w = i; w &lt;= j; ++w)
59                 if(count2[a[w]])&amp;#123;flag = 1; break;&amp;#125;//区间村咋重复数字，break
60                 else &amp;#123;++count2[a[w]]; ++count[a[w]]; Min2 = min(Min2, a[w]); Max = max(Max, a[w]);&amp;#125;//查找该区间最大与最小值
61             if(flag)continue;
62             sum[Min2 - 1] = 0;
63         
64             for(int w = Min2; w &lt;= Max; ++w)sum[w] = sum[w - 1] + count[w];
65 //区间求和(求个数）！！很巧妙！：也就是求区间的合并次数 
66             for(int k = i; k &lt; j; ++k)
67             &amp;#123;
68                 --count2[a[k]];
69                 Min1 = min(Min1, a[k]);
70                 if(Min2 == a[k])for(Min2; !count2[Min2]; ++Min2);
71 
72                 ans = min(ans, g[i][k] + g[k + 1][j] + (j - i + 1) -           sum[max(Min1, Min2) - 1]);
73             &amp;#125;
74             g[i][j] = ans;
75         &amp;#125;
76     &amp;#125;
77 
78     f[0] = 0; 
79     for(int i = 1; i &lt;= n; ++i)f[i] = INF;
80     if(a[1] == 1)f[1] = 0;
81     for(int i = 2; i &lt;= n; ++i)
82     &amp;#123;
83         for(int j = 0; j &lt; i; ++j)
84             if(check(j + 1, i))&amp;#123;f[i] = min(f[i], f[j] + g[j + 1][i]);&amp;#125;
85     &amp;#125;
86 
87 
88     if(f[n] != INF) printf(&quot;%d\n&quot;, f[n]);
89     else printf(&quot;Impossible\n&quot;);
90     return 0;
91 &amp;#125;
</code></pre>
<p><a target="_blank" rel="noopener" href="https://blog.csdn.net/weixin_30344131/article/details/96302655">https://blog.csdn.net/weixin_30344131/article/details/96302655</a></p>
<h2 id="能量项链："><a href="#能量项链：" class="headerlink" title="能量项链："></a>能量项链：</h2><p>这是一个环状的矩阵相乘问题</p>
<p>在遇到一道题的时候，可以用dfs思想做的，不放尝试一下动态规划</p>
<p>可以用动态规划做的，</p>
<p>就要考虑，用什么DP，几维DP，那些属性作为数组坐标</p>
<pre><code class="lang-c++">#include&lt;iostream&gt;
#include&lt;algorithm&gt;
using namespace std;

typedef long long int ll;
struct node&amp;#123;
    int x,y;
&amp;#125;a[100010]; 

ll F[210][210];
int main()&amp;#123;
    int m,n;
    int i,j,k;

    cin&gt;&gt;n;
    for(i=1;i&lt;=n;i++)&amp;#123;
       cin&gt;&gt;k;
       a[i].x=k;
       a[i-1].y=k;


    &amp;#125;
    a[n].y=a[1].x;
    for(i=n+1;i&lt;=2*n;i++)&amp;#123;
        a[i]=a[i-n];
    &amp;#125;
//    a[0]=a[n];
    for(i=1;i&lt;=n-1;i++)&amp;#123;//步长
        for(j=1;j&lt;=2*n-i;j++)&amp;#123;//起始点
             for(k=j;k&lt;=j+i-1;k++)&amp;#123;
                 F[j][j+i]=max(F[j][k]+F[k+1][j+i]+a[j].x*a[k].y*a[j+i].y,F[j][j+i]);
                 //cout&lt;&lt;j&lt;&lt;&quot; &quot;&lt;&lt;j+i&lt;&lt;&quot; &quot;&lt;&lt;k&lt;&lt;&quot; &quot;&lt;&lt;F[i][j]&lt;&lt;endl; 
             &amp;#125; 
        &amp;#125; 
    &amp;#125;

    ll maxn=0;
    for(i=1;i&lt;=n;i++)&amp;#123;
        maxn=max(F[i][i+n-1],maxn);
    &amp;#125;
    cout&lt;&lt;maxn;
&amp;#125;
</code></pre>
<p>分析一下下面的算法为何不对：</p>
<pre><code class="lang-c++">    for(i=1;i&lt;=2*n;i++)&amp;#123;
        for(j=i+1;j&lt;=2*n;j++)&amp;#123;
            for(k=j-1;k&gt;=i;k--)&amp;#123;
                if(j-i&lt;n) &amp;#123;
                    F[i][j]=max(F[i][k]+F[k+1][j]+a[i].x*a[k].y*a[j].y,F[i][j]);
                &amp;#125;

            &amp;#125;
        &amp;#125;
    &amp;#125;
</code></pre>
<h2 id="石子合并："><a href="#石子合并：" class="headerlink" title="石子合并："></a>石子合并：</h2><blockquote>
<p>错误原因：j+1;j&lt;n-1;j++</p>
</blockquote>
<pre><code class="lang-c++">for(i=1;i&lt;=n-1;i++)&amp;#123;//步伐 
        for(j=1;j&lt;=n-i;j++)&amp;#123;//起始点 
            for(k=j;k&lt;j+i;k++)&amp;#123;
                if(F[j][j+i]) F[j][j+i]=min(F[j][k]+F[k+1][j+i]+sum[j+i]-sum[j-1],F[j][j+i]);
                else F[j][j+i]=F[j][k]+F[k+1][j+i]+sum[j+i]-sum[j-1];
        &amp;#125;
    &amp;#125;
&amp;#125;
 cout&lt;&lt;F[1][n];
</code></pre>
<h2 id="九宫重排："><a href="#九宫重排：" class="headerlink" title="九宫重排："></a>九宫重排：</h2><p>这道题，问的是：</p>
<p>本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。</p>
<p>最少，结合题意，一般就是动态规划或者dfs或者bfs</p>
<p>最少问题是典型的bfs问题</p>
<p>与前面学的bfs问题不同的是，每走一步（搜索一步，当前的局面会改变，且走的不同方向影响着当前的局面）</p>
<p>为此，为了处理这种情况，首先，我们应该把每一种局面给存起来，以防下一步在意出现这种局面，造成死循环</p>
<p>再者，我们观察到：</p>
<p><del>一棵树 的子节点是面临着相同的局面，但是不同树是不同的，因此，我们学会了，在进行每一步bfs时，要把同一深度的结点全部入队且 全部出队，（出队的时候可以继续入队子节点，但是你要明白阈值在那里）然后进行下一步，因此引入双层while</del></p>
<p><del>还有一个问题，就是：避免越界</del></p>
<p>为了记录当前的次数，可以将某一深度全部入队并出队在进行下一步</p>
<p>以上分析：</p>
<p>我们写一下步骤：</p>
<ol>
<li><p>输入并记录子节点的位置，入队</p>
</li>
<li><p>从队中第一结点开始：</p>
<p>(1).判断是否是终点，是，return，否则，将将当前局面存起来</p>
<p>(2).将符合要求的子节点入队，并依次出队</p>
</li>
</ol>
<pre><code class="lang-c++">#include &lt;stdio.h&gt;
#include &lt;memory.h&gt;
#include &lt;math.h&gt;
#include &lt;string&gt;
#include &lt;string.h&gt;
#include &lt;vector&gt;
#include &lt;set&gt;
#include &lt;stack&gt;
#include &lt;queue&gt;
#include &lt;algorithm&gt;
#include &lt;map&gt;


#define I scanf
#define OL puts
#define O printf
#define F(a,b,c) for(a=b;a&lt;c;a++)
#define FF(a,b) for(a=0;a&lt;b;a++)
#define FG(a,b) for(a=b-1;a&gt;=0;a--)
#define LEN 100
#define MAX 0x06FFFFFF
#define V vector&lt;int&gt;

typedef long long ll;

using namespace std;

set&lt;string&gt; vis; 

bool notVis(string s)&amp;#123;//判断当前的状态在前面是否遇到过
    if(vis.find(s)==vis.end())&amp;#123;
        vis.insert(s);
        return 1;
    &amp;#125;else&amp;#123;
        return 0;
    &amp;#125;
&amp;#125;

int main()&amp;#123;
//    freopen(&quot;D:/CbWorkspace/blue_bridge/九宫重排_2.txt&quot;,&quot;r&quot;,stdin);
    char buf[10];
    gets(buf);
    string S(buf);
    gets(buf);
    string E(buf);
    queue&lt;string&gt; q;
    q.push(S);
    int cnt=0;
    while(!q.empty())&amp;#123;
        int sz=q.size();
        while(sz--)&amp;#123;
            string t=q.front();
            q.pop();
            if(t==E)&amp;#123;
                O(&quot;%d\n&quot;,cnt);
                return 0;
            &amp;#125;
            int pos=t.find(&#39;.&#39;);
            if(pos&gt;=3)&amp;#123;//上 
                string tmp=t;
                swap(tmp[pos],tmp[pos-3]);
                if(notVis(tmp)) q.push(tmp);
            &amp;#125;
            if(pos&lt;6)&amp;#123;//下 
                string tmp=t;
                swap(tmp[pos],tmp[pos+3]);
                if(notVis(tmp)) q.push(tmp);
            &amp;#125;
            if(pos%3&gt;0)&amp;#123;//左 
                string tmp=t;
                swap(tmp[pos],tmp[pos-1]);
                if(notVis(tmp)) q.push(tmp);
            &amp;#125;
            if(pos%3&lt;2)&amp;#123;//右
                string tmp=t;
                swap(tmp[pos],tmp[pos+1]);
                if(notVis(tmp)) q.push(tmp);
            &amp;#125;             
        &amp;#125;
        cnt++;
    &amp;#125;
    O(&quot;%d\n&quot;,-1);
    return 0;
&amp;#125;
</code></pre>
<h2 id="最大值路径"><a href="#最大值路径" class="headerlink" title="最大值路径"></a>最大值路径</h2><p>这种只有两个方向的，可以考虑动态规划</p>
<h2 id=""><a href="#" class="headerlink" title=" "></a> </h2><h2 id="矩阵翻转（动态规划）"><a href="#矩阵翻转（动态规划）" class="headerlink" title="矩阵翻转（动态规划）"></a>矩阵翻转（动态规划）</h2><h3 id="（未解决）"><a href="#（未解决）" class="headerlink" title="（未解决）"></a>（未解决）</h3><p>问题描述</p>
<p>Ciel有一个N*N的矩阵，每个格子里都有一个整数。</p>
<p>N是一个奇数，设X = (N+1)/2。Ciel每次都可以做这样的一次操作：他从矩阵选出一个X*X的子矩阵，并将这个子矩阵中的所有整数都乘以-1。</p>
<p>现在问你经过一些操作之后，矩阵中所有数的和最大可以为多少。</p>
<p>输入格式</p>
<p>第一行为一个正整数N。</p>
<p>接下来N行每行有N个整数，表示初始矩阵中的数字。每个数的绝对值不超过1000。</p>
<p>输出格式</p>
<p>输出一个整数，表示操作后矩阵中所有数之和的最大值。</p>
<p>样例输入</p>
<p>3<br>-1 -1 1<br>-1 1 -1<br>1 -1 -1</p>
<p>样例输出</p>
<p>9</p>
<pre><code class="lang-c++">#include&lt;cstdio&gt;
#include&lt;algorithm&gt;
#include&lt;cstring&gt;
using namespace std;
const int N=50;
int n,m,a[N][N],f[N][N];
int solve_j(int j)&amp;#123;
 int ans=0;
    for(int i=0;i&lt;m;i++)&amp;#123;
  int temp=0;
  f[i][j]=1; 
  temp+=f[i][j]*a[i][j];

  f[i+m+1][j]=f[m][j]*f[i][j]; 
        temp+=f[i+m+1][j]*a[i+m+1][j];

  f[i][j+m+1]=f[i][m]*f[i][j];
  temp+=f[i][j+m+1]*a[i][j+m+1];

  f[i+m+1][j+m+1]=f[m][j+m+1]*f[i][j+m+1];
  temp+=f[i+m+1][j+m+1]*a[i+m+1][j+m+1];

  if(temp&lt;0) temp=-temp;
  ans+=temp;
 &amp;#125;
 return ans;
&amp;#125;
int solve(int mask)&amp;#123;
    int ans=0;
 for(int i=0;i&lt;=m;i++)&amp;#123;
     f[i][m]=(mask&amp;(1&lt;&lt;i))?-1:1;
  ans+=a[i][m]*f[i][m];
 &amp;#125;
 for(int i=m+1;i&lt;n;i++)&amp;#123;
  f[i][m]=f[m][m]*f[i-m-1][m];
     ans+=a[i][m]*f[i][m];
 &amp;#125;
 for(int j=0;j&lt;m;j++)&amp;#123;
  int temp;
     f[m][j]=1;
        f[m][j+m+1]=f[m][j]*f[m][m];
  temp=solve_j(j)+f[m][j]*a[m][j]+f[m][j+m+1]*a[m][j+m+1];
        f[m][j]=-1;
  f[m][j+m+1]=f[m][j]*f[m][m];
  temp=max(temp,solve_j(j)+f[m][j]*a[m][j]+f[m][j+m+1]*a[m][j+m+1]);
  ans+=temp;
 &amp;#125;
 return ans;
&amp;#125;
int main()&amp;#123;
 while(scanf(&quot;%d&quot;,&amp;n)==1)&amp;#123;
     int ans=-10000000;
  m=n/2;
        for(int i=0;i&lt;n;i++)
   for(int j=0;j&lt;n;j++)
    scanf(&quot;%d&quot;,&amp;a[i][j]);
  int temp=(1&lt;&lt;(m+1));//左移符号 2^（m+1) m为中值
        for(int mask=0;mask&lt;temp;mask++)
   ans=max(ans,solve(mask));
  printf(&quot;%d\n&quot;,ans);
 &amp;#125;
    return 0;
&amp;#125;
</code></pre>
<p>3.31:<br>浮点数：</p>
<p><img src="https://gitee.com/moluggg/image/raw/master/20200331222641.png"/></p>
<p>明摆着学习一个新输出方法：</p>
<p>printf(“%E”,ans);</p>
<p><img src="https://gitee.com/moluggg/image/raw/master/20200331222825.png"/></p>
<p>精确数字的输入输出不能用cin,cout</p>
<h2 id="疑问？？？"><a href="#疑问？？？" class="headerlink" title="疑问？？？"></a>疑问？？？</h2><p><img src="/tmp/1586256142129.png" alt="1586256142129"></p>
<p>为什么没有函数包装，就显示：链表’Head’ does not name a type</p>
<h2 id="学习string几个函数："><a href="#学习string几个函数：" class="headerlink" title="学习string几个函数："></a>学习string几个函数：</h2><p>s1.erase(i,n)//从i开始删除n个元素</p>
<p>s.substr(i,n)//从i开始截取n个元素</p>
<pre><code>s.replace(pos, n, s1)    用s1替换s中从pos开始（包括0）的n个字符的子串
</code></pre><p>s.find(s1)         查找s中第一次出现s1的位置，并返回（包括0）</p>
<pre><code class="lang-c++">string s1,s2;
cin&gt;&gt;s1&gt;&gt;s2;
int k1=s1.length();
int k2=s2.length();
int i=0;
while(i&lt;=k1-k2)&amp;#123;

   if(s1[i]==s2[0]&amp;&amp;s1.substr(i,k2)==s2) s1=s1.erase(i,k2);
    else i++;

&amp;#125;
cout&lt;&lt;s1;
return 0;
&amp;#125;
</code></pre>
<h2 id="最小生成树："><a href="#最小生成树：" class="headerlink" title="最小生成树："></a>最小生成树：</h2><h3 id="并查集：-三函数表示"><a href="#并查集：-三函数表示" class="headerlink" title="并查集：(三函数表示)"></a>并查集：(三函数表示)</h3><p>祖先：find</p>
<p>并 ：merge</p>
<p>查：check</p>
<pre><code class="lang-c++">int find (int x)&amp;#123;//原来查找祖先是并查集操作
    if(x==F[x]) return x;
    F[x]=find(F[x]);
     return find(F[x]);
&amp;#125;
bool check(int x,int y)&amp;#123;
    if(find(x)==find(y)) return 0;
    else return 1;

&amp;#125;
void merge (int x,int y)&amp;#123;
    F[find (x)]=find(y);//x的祖先指向y，现在xy共同的祖先是find（y)
&amp;#125;
</code></pre>
<h3 id="克鲁斯卡尔："><a href="#克鲁斯卡尔：" class="headerlink" title="克鲁斯卡尔："></a>克鲁斯卡尔：</h3><pre><code class="lang-c++">int kruskal()&amp;#123;
    int sum=0;
    int cnt=0;//记录边数
    //int t1,t2;
    int i;
    for(i=1;i&lt;=M;i++)&amp;#123;

      if(check(side[i].from,side[i].to)) &amp;#123;
          merge(side[i].from,side[i].to);cnt++;
          sum+=side[i].distance;
      &amp;#125;
      else &amp;#123;
          continue;
      &amp;#125;
      if(cnt==M-1) break;
    &amp;#125;
    return sum;
&amp;#125;
</code></pre>
<h3 id="由点遍历边的三数组："><a href="#由点遍历边的三数组：" class="headerlink" title="由点遍历边的三数组："></a>由点遍历边的三数组：</h3><p>（本体没有涉及，复习一下）</p>
<pre><code class="lang-c++">void sidee(int x,int y,int m)&amp;#123;//遍历点的做法

   to[++cnt]=y;
   nextt[cnt]=Head[x];
   Head[x]=cnt;
   dis[cnt]=m;
&amp;#125;
int FF()&amp;#123;
    int i;
      for (i=1;i&lt;=3;i++)&amp;#123;
        int x,y;
        cin&gt;&gt;x&gt;&gt;y&gt;&gt;m;
        sidee(x,y,m);
        sidee(y,x,m);

    &amp;#125;
    i=2;
    for (i=Head[i];i!=0;i=nextt[i])&amp;#123;
        cout&lt;&lt;dis[i];
    &amp;#125;
    return 0;
&amp;#125;
</code></pre>
<p>总的函数：</p>
<pre><code>//邻接矩阵表示图（大数据不建议用）
int Head[50001];
int to[50001];
int nextt[50001];
int dis[50001];
int cnt=0;
int F[500001];
int N,M,x,y,z;

struct node &amp;#123;//遍历边的
    int to,from;
    int distance ;
&amp;#125;side [50001];



bool cmp(node x,node y)&amp;#123;
    return x.distance&lt;y.distance;
&amp;#125;
int kruskal()&amp;#123;
    int sum=0;
    int cnt=0;//记录边数
    //int t1,t2;
    int i;
    for(i=1;i&lt;=M;i++)&amp;#123;

      if(check(side[i].from,side[i].to)) &amp;#123;
          merge(side[i].from,side[i].to);cnt++;
          sum+=side[i].distance;
      &amp;#125;
      else &amp;#123;
          continue;
      &amp;#125;
      if(cnt==M-1) break;
    &amp;#125;
    return sum;
&amp;#125;
int main()
&amp;#123;
    int i;

    cin&gt;&gt;N&gt;&gt;M;

    for(i=1;i&lt;=M;i++)&amp;#123;
        cin&gt;&gt;x&gt;&gt;y&gt;&gt;z;
        side[i].from=x;
        side[i].to=y;
        side[i].distance=z;
    &amp;#125;
    sort(side +1,side +1+M,cmp);
    //并查集：
    for (i=1;i&lt;=N;i++) F[i]=i;//初始化

    i=kruskal();
    cout&lt;&lt;i;

    return 0;

&amp;#125;
</code></pre><p>不知为何错了？</p>
<pre><code class="lang-c++">#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;iostream&gt;
#include &lt;cmath&gt;
#include &lt;vector&gt;
#include &lt;set&gt;
#include&lt;string.h&gt;
#include &lt;map&gt;
#include &lt;algorithm&gt;
#include&lt;cstddef&gt;
using namespace std;

int dx[40]=&amp;#123;0,0,1,-1,1,-1,1,-1&amp;#125;;
int dy[40]=&amp;#123;1,-1,0,0,-1,1,1,-1&amp;#125;;
int F[100010];
int bian[100010];
int g=0;
struct node &amp;#123;
    int x,y;
&amp;#125;a[1000010];
vector &lt;node&gt;q;
struct LNode&amp;#123;
   int to,from;
   int distance ;//边
&amp;#125;side [1000010],true_side[100010];
//并查集的三函数
int find (int x)&amp;#123;

    if(x== F[x]) return x;//...........................(1)
    F[x]=find(F[x]);
    return find(F[x]);
&amp;#125;

int check(int x,int y)&amp;#123;
  if(find(x)==find(y)) return 0;
  else return 1;
&amp;#125;
void merge(int x,int y)&amp;#123;
    F[find(x)]=find(y);
&amp;#125;
int judge(int x1,int y1,int x2,int y2)&amp;#123;
    if(abs(x1-x2)&lt;=1||abs(y1-y2)&lt;=1) return 1;
    return 0;
&amp;#125;
int cal(int x1,int y1,int x2,int y2)&amp;#123;//计算连点之间的距离

    if(abs(x1-x2)&lt;=1&amp;&amp;abs(y1-y2)&gt;=abs(x1-x2))&amp;#123;
                            //...........................(2)
        return abs(y1-y2)-1;
    &amp;#125;
    else &amp;#123;
        return abs(x1-x2)-1;
    &amp;#125;
&amp;#125;
bool cmp(LNode x,LNode y)&amp;#123;
    return x.distance &lt;y.distance ;
&amp;#125;
int main()&amp;#123;
   int n,m;
   //int num=0;
   char mapp[500][500];

   while(cin&gt;&gt;n&gt;&gt;m&amp;&amp;n!=0&amp;&amp;m!=0)&amp;#123;
   int i,j;
   int cnt=0;
   memset(mapp,&#39;0&#39;,sizeof(mapp));
   q.clear();

   for(i=1;i&lt;=n;i++)&amp;#123;
       for (j=1;j&lt;=m;j++)&amp;#123;
          // cout&lt;&lt;i*j&lt;&lt;endl;
          cin&gt;&gt;mapp[i][j];
          node t;
          t.x=i;
          t.y=j;
          if(mapp[i][j]==&#39;#&#39;) q.push_back(t);//?????
       &amp;#125;
   &amp;#125;

  //return 0;

   //寻找所有的边，并建立联系
   for(i=0;i&lt;q.size()-1;i++)&amp;#123;

       int k1=q[i].x;
       int k2=q[i].y;

      // bian[k1][k2]=i;
       for (j=i+1;j&lt;q.size();j++)&amp;#123;//
          int l1=q[j].x;
          int l2=q[j].y;//
                    //...........................(3)
          if(judge(k1,k2,l1,l2)) &amp;#123;
              side[++cnt].from=i;
              side[cnt].to=j;
              side[cnt].distance=cal(k1,k2,l1,l2);

          &amp;#125;

       &amp;#125;
   &amp;#125;

   //开始：
   int sum=0;
   int len=0;
   for(i=0;i&lt;q.size();i++) F[i]=i;//初始化
   sort(side+1,side+1+cnt,cmp);

   for(i=1;i&lt;=cnt;i++)&amp;#123;

       int k1=side[i].to;
       int k2=side[i].from;
       //cout&lt;&lt;k1&lt;&lt;&quot; &quot;&lt;&lt;k2&lt;&lt;&quot; &quot;&lt;&lt;side[i].distance&lt;&lt;endl;
     // cout&lt;&lt;F[k1]&lt;&lt;&quot; &quot;&lt;&lt;F[k2]&lt;&lt;endl;
       if(check(k1,k2))&amp;#123;
         // cout&lt;&lt;k1&lt;&lt;&quot; &quot;&lt;&lt;k2&lt;&lt;endl;
           merge(k1,k2);

           int flag=0;
           for(j=0;j&lt;8;j++)&amp;#123;
               if(q[k1].x+dx[j]==q[k2].x&amp;&amp;q[k1].y+dy[j]==q[k2].y) flag=1;

           &amp;#125;
           //cout&lt;&lt;k1&lt;&lt;&quot; &quot;&lt;&lt;k2&lt;&lt;&quot; &quot;&lt;&lt;flag&lt;&lt;endl;
           if(flag==0) sum++,len+=side[i].distance;
       &amp;#125;
   &amp;#125;

   //判断费连通图有多少个：
   int vis[1000010];
   memset(vis,0,sizeof(vis));
   int ans=0;
   for(i=0;i&lt;q.size();i++)&amp;#123;
      // cout&lt;&lt;q[i].x&lt;&lt;&quot; &quot;&lt;&lt;q[i].y&lt;&lt;&quot; &quot;&lt;&lt;F[i]&lt;&lt;&quot; 123&quot;&lt;&lt;endl;
       if(vis[F[i]]==0) &amp;#123;
           ans++;
           //cout&lt;&lt;F[i]&lt;&lt;&quot; &quot;;
           vis[F[i]]=1;
       &amp;#125;
   &amp;#125;

   cout&lt;&lt;&quot;City &quot;&lt;&lt;++g&lt;&lt;endl;
   if(sum&gt;=1) cout&lt;&lt; sum&lt;&lt;&quot; bridges of total length &quot;&lt;&lt;len&lt;&lt;endl;

   else if(sum==0&amp;&amp;ans&gt;1) cout&lt;&lt;&quot;No bridges are possible.&quot;&lt;&lt;endl;

   else cout&lt;&lt;&quot;No bridges are needed.&quot;&lt;&lt;endl;

   if(ans&gt;1) cout&lt;&lt;ans&lt;&lt;&quot; disconnected groups&quot;&lt;&lt;endl;
   &amp;#125;
   return 0;
&amp;#125;
</code></pre>
<p>一些粗心错误：</p>
<p>（1）for 循环你总是喜欢写i的j++携程i++</p>
<p>   (2)   代码里面的(x=F[x] ) 你写成了x= find(x)</p>

      
       <hr><span style="font-style: italic;color: gray;"> 转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 2572876783@qq.com </span>
    </div>
</article>


<p>
    <a  class="dashang" onclick="dashangToggle()">💰</a>
</p>






    
        <!-- MathJax配置，可通过单美元符号书写行内公式等 -->
<script type="text/x-mathjax-config">
    MathJax.Hub.Config({
    "HTML-CSS": {
        preferredFont: "TeX",
        availableFonts: ["STIX","TeX"],
        linebreaks: { automatic:true },
        EqnChunk: (MathJax.Hub.Browser.isMobile ? 10 : 50)
    },
    tex2jax: {
        inlineMath: [ ["$", "$"], ["\\(","\\)"] ],
        processEscapes: true,
        ignoreClass: "tex2jax_ignore|dno",
        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
    },
    TeX: {
        equationNumbers: { autoNumber: "AMS" },
        noUndefined: { attributes: { mathcolor: "red", mathbackground: "#FFEEEE", mathsize: "90%" } },
        Macros: { href: "{}" }
    },
    messageStyle: "none"
    });
</script>
<!-- 给MathJax元素添加has-jax class -->
<script type="text/x-mathjax-config">
    MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for(i=0; i < all.length; i += 1) {
            all[i].SourceElement().parentNode.className += ' has-jax';
        }
    });
</script>
<!-- 通过连接CDN加载MathJax的js代码 -->
<script type="text/javascript" async
        src="//cdn.jsdelivr.net/npm/mathjax@2.7.8/unpacked/MathJax.js?config=TeX-MML-AM_CHTML">
</script>
<input type="hidden" id="MathJax-js"
        value="//cdn.jsdelivr.net/npm/mathjax@2.7.8/unpacked/MathJax.js?config=TeX-MML-AM_CHTML">
</input>
    




    </div>
    <div class="copyright">
        <p class="footer-entry">
    ©2016-2020 MOLU
</p>
<p class="footer-entry">Built with <a href="https://hexo.io/" target="_blank">Hexo</a> and <a href="https://github.com/yelog/hexo-theme-3-hexo" target="_blank">3-hexo</a> theme</p>

    </div>
    <div class="full-toc">
        <button class="full" data-title="切换全屏 快捷键 s"><span class="min "></span></button>
<a class="" id="rocket" ></a>

    </div>
</div>

<div class="hide_box" onclick="dashangToggle()"></div>
<div class="shang_box">
    <a class="shang_close"  onclick="dashangToggle()">×</a>
    <div class="shang_tit">
        <p>Help us with donation</p>
    </div>
    <div class="shang_payimg">
        <div class="pay_img">
            <img src="/img/alipay.jpg" class="alipay" title="扫码支持">
            <img src="/img/weixin.jpg" class="weixin" title="扫码支持">
        </div>
    </div>
    <div class="shang_payselect">
        <span><label><input type="radio" name="pay" checked value="alipay">alipay</label></span><span><label><input type="radio" name="pay" value="weixin">weixin</label></span>
    </div>
</div>


</body>
<script src="/js/jquery.pjax.js?v=1.1.0" ></script>

<script src="/js/script.js?v=1.1.0" ></script>
<script>
    var img_resize = 'default';
    function initArticle() {
        /*渲染对应的表格样式*/
        
            $("#post .pjax table").addClass("green_title");
        

        /*渲染打赏样式*/
        
        $("input[name=pay]").on("click", function () {
            if($("input[name=pay]:checked").val()=="weixin"){
                $(".shang_box .shang_payimg .pay_img").addClass("weixin_img");
            } else {
                $(".shang_box .shang_payimg .pay_img").removeClass("weixin_img");
            }
        })
        

        /*高亮代码块行号*/
        

        /*访问数量*/
        
        $.getScript("//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js");
        

        /*代码高亮，行号对齐*/
        $('.pre-numbering').css('line-height',$('.has-numbering').css('line-height'));

        
        
    }

    /*打赏页面隐藏与展示*/
    
    function dashangToggle() {
        $(".shang_box").fadeToggle();
        $(".hide_box").fadeToggle();
    }
    

</script>

<!--加入行号的高亮代码块样式-->

<!--自定义样式设置-->
<style>
    
    
    .nav {
        width: 542px;
    }
    .nav.fullscreen {
        margin-left: -542px;
    }
    .nav-left {
        width: 120px;
    }
    
    
    @media screen and (max-width: 1468px) {
        .nav {
            width: 492px;
        }
        .nav.fullscreen {
            margin-left: -492px;
        }
        .nav-left {
            width: 100px;
        }
    }
    
    
    @media screen and (max-width: 1024px) {
        .nav {
            width: 492px;
            margin-left: -492px
        }
        .nav.fullscreen {
            margin-left: 0;
        }
    }
    
    @media screen and (max-width: 426px) {
        .nav {
            width: 100%;
        }
        .nav-left {
            width: 100%;
        }
    }
    
    
    .nav-right .title-list nav a .post-title, .nav-right .title-list #local-search-result a .post-title {
        color: #383636;
    }
    
    
    .nav-right .title-list nav a .post-date, .nav-right .title-list #local-search-result a .post-date {
        color: #5e5e5f;
    }
    
    
    .nav-right nav a.hover, #local-search-result a.hover{
        background-color: #e2e0e0;
    }
    
    

    /*列表样式*/
    

    /* 背景图样式 */
    
    


    /*引用块样式*/
    

    /*文章列表背景图*/
    

    
</style>







</html>
